package 面试经典150题.链表;

import common.ListNode;

/*我们要把反转后的链表拼接回去，实际上就是让reversePre的next指针指向reverseTail，让reverseHead的next指针指向reverseNext。

        题目中的left和right的数值分别表示第几个节点，我们可以使用一个变量count来统计当前节点是第几个节点，初始值为1。
        当反转区间的头节点为head时，head之前没有节点了，为了统一，我们在头节点之前引入伪头节点pre。

        作者：画图小匠
        链接：https://leetcode.cn/problems/reverse-linked-list-ii/solutions/2397023/javapython3cfan-zhuan-lian-biao-chai-fen-ofh0/
        来源：力扣（LeetCode）
        著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。*/

public class T92反转链表II {

    public ListNode reverseBetween(ListNode head, int left, int right) {
        //定义一个虚拟头结点,指向head头结点
        ListNode pre = new ListNode();
        //让翻转区间头结点的上一个节点也一开始也指向虚拟头结点
        ListNode reversePre = pre;
        //节点编号
        int count = 1;
        //遍历链表，让reversePre指向left的上一个节点
        while (count < left) {
            reversePre = reversePre.next;
            count++;
        }
        //获取翻转区间的头结点
        ListNode reverseHead = reversePre.next;
        ListNode cur = reverseHead;
        //定义一个last节点指向null
        ListNode last = null;
        //定义一个next节点，用于指向下一个节点
        ListNode next;
        //链表翻转模版 遍历完了之后cur节点应该指向的是翻转区间的下一个节点
        while (count <= right) {
            //1.先保存当前节点的next节点
            next = cur.next;
            //2.断掉当前节点的指针链接
            cur.next = last;
            //last指针移动到cur指针
            last = cur;
            //cur指针移动到next指针
            cur = next;
            count++;
        }
        //连接链表
        // 反转区间前一个节点应该连接到反转区间的最后一个节点，即当前的last
        reversePre.next=last;
        // 反转区间的头节点应该连接到反转区间的下一个节点，即当前的next
        reverseHead.next=cur;
        return pre.next;
    }
}
